1520s, "accompany," see go (v.) + together (adv.). From 1710 as "agree with, harmonize with;" 1899 as "be courting."
go on
go out
go over
go south
go through
go together
go west
Goa
goad
go-ahead
goal